package com.aqie.arithmetic.math;

import com.aqie.libs.StdOut;

import java.util.Stack;

/**
 * Dijkstra 双栈算术表达式求值算法
 */
public class Evaluate {
    /**
     * 1. 操作数压入栈
     * 2. 运算符入栈
     * 3. 忽略左括号
     * 4. 遇到右括号，弹出运算符，弹出所需数量的操作数，
     *    并将运算符和操作数的运算结果压入操作数栈
     * @param str 必须是整数
     */
    public static void evaluate(String str){
        Stack<Character> ops = new Stack<>();
        Stack<Double> vals = new Stack<>();
        for (int i = 0; i < str.length(); i++){
            char s = str.charAt(i);
            switch (s) {
                case '(':
                    break;
                case ' ':
                    break;
                case '+':
                    ops.push(s);
                    break;
                case '-':
                    ops.push(s);
                    break;
                case '*':
                    ops.push(s);
                    break;
                case '/':
                    ops.push(s);
                    break;
                case '#':
                    ops.push(s);
                    break;
                case ')':
                    Character op = ops.pop();
                    double v = vals.pop();
                    if (op.equals('+')) v = vals.pop() + v;
                    else if (op.equals('-')) v = vals.pop() - v;
                    else if (op.equals('*')) v = vals.pop() * v;
                    else if (op.equals('/')) v = vals.pop() / v;
                    else if (op.equals('#')) v = Math.sqrt(v);
                    vals.push(v);
                    break;
                default:
                    // 操作数入栈
                    vals.push(Double.parseDouble(s + ""));
                    break;
            }
        }
        StdOut.println(vals.pop());
    }

    public static void main(String[] args) {
        String str = "(1 + ((2 + 3) * ( 4 * 5)))";  // 101
        // str = "1+(2+3)*(4*5)";                   // todo 解析这个数学表达式
        str = "((1 + #(5)) / 2)";                   // 1.618
        evaluate(str);
    }
}
